package com.tucc.hello.leetcode.no1_400.no1_200.no21_40.no31;

import java.util.Arrays;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {5, 4 ,2, 1, 3};
        solution.nextPermutation(nums);
        Arrays.stream(nums).mapToObj(o -> o + " ").forEach(System.out::print);
        System.out.println();
    }

    public void nextPermutation(int[] nums) {
        int smallI = nums.length - 1;
        while (smallI >= 0) {
            if (smallI - 1 >= 0) {
                if (nums[smallI] > nums[smallI - 1]) {
                    smallI = smallI - 1;
                    break;
                }
            } else {
                smallI = -1;
                break;
            }
            smallI--;
        }
        if (smallI >= 0) {
            int bigI = -1;
            for (int i = nums.length - 1; i > smallI; i--) {
                if (nums[i] > nums[smallI]) {
                    bigI = i;
                    break;
                }
            }
            swap(nums, smallI, bigI);
        }

        int left = smallI + 1;
        int right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
